package gold.digger;

import gold.vo.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC515 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目直接用别人代码，自己只理解思想
     * 很优雅的解法，非常值得一看
     * @return:
     */
    class Solution {
        public List<Integer> largestValues(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            helper(root, res, 1);
            return res;
        }

        //level表示的是第几层，集合res中的第一个数据表示的是
        // 第一层的最大值，第二个数据表示的是第二层的最大值……
        private void helper(TreeNode root, List<Integer> res, int level) {
            if (root == null) return;
            //如果走到下一层了直接加入到集合中
            if (level == res.size() + 1) {
                res.add(root.val);
            } else {
                //注意：我们的level是从1开始的，也就是说root
                // 是第一层，而集合list的下标是从0开始的，
                // 所以这里level要减1。
                // Math.max(res.get(level - 1), root.val)表示的
                // 是遍历到的第level层的root.val值和集合中的第level
                // 个元素的值哪个大，就要哪个。
                res.set(level - 1, Math.max(res.get(level - 1), root.val));
            }
            //下面两行是DFS的核心代码
            helper(root.left, res, level + 1);
            helper(root.right, res, level + 1);
        }

    }

    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC515 an = new LC515();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
